package listbyorder.access201_300.test212;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/23 21:02
 */
public class Solution1 {

    public List<String> findWords(char[][] board,String[] words) {
        List<String> ans = new ArrayList<>();
        if (board == null || board.length == 0 || board[0].length == 0 || words == null || words.length == 0) {
            return ans;
        }
        for (String word : words) {
            if (isExists(board, word.toCharArray())) {
                ans.add(word);
            }
        }
        return ans;
    }

    // 判断一个单词在二维数组中是否存在
    private boolean isExists(char[][] board, char[] chars) {
        int r = board.length;
        int c = board[0].length;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (dfs(board, i, j, chars, 0, new boolean[r][c])) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int r, int c, char[] chars, int index, boolean[][] flag) {
        int row = board.length;
        int col = board[0].length;
        if (index == chars.length) return true;
        if (r == -1 || r == row || c == -1 || c == col || board[r][c] != chars[index] || flag[r][c]) {
            return false;
        }
        flag[r][c] = true;
        if (dfs(board, r + 1, c, chars, index + 1, flag) ||
                dfs(board, r - 1, c, chars, index + 1, flag) ||
                dfs(board, r, c + 1, chars, index + 1, flag) ||
                dfs(board, r, c - 1, chars, index + 1, flag)) {
            return true;
        }
        flag[r][c] = false;   // 这里需要发生回溯
        return false;
    }
}
